1. Technical Field
The present disclosure relates to managing data stored in blocks of a nonvolatile memory through a file translation layer.
2. Description of the Related Art
FIG. 1A illustrates a related-art method of storing data in a memory device using a logical-to-physical page translation. FIG. 1B illustrates the related-art method of FIG. 1A pictorially. According to the method, a flash translation layer (FTL) 100 receives 110 from a host file system (HFS) 105 a logical page number (LPN) and data. Flash translation layer 100 stores 120 the received data in a memory space identified by a physical page number (PPN) and associates 130 the LPN with the PPN where the data is stored. The associations among LPNs and PPNs for all pages of the memory device are maintained in a logical-to-physical address table by flash translation layer 100.
FIG. 1C illustrates a related-art method of retrieving data stored in a memory device using a logical-to-physical page translation. FIG. 1D illustrates the related-art method of FIG. 1C pictorially. According to the method, flash translation layer 100 receives 140 from host file system 105 an LPN. Flash translation layer 100 identifies 150 the PPN associated with the LPN received from host filing system 105. Such identification is made by referencing the logical-to-physical address table using the LPN as an index value. Flash translation layer 100 retrieves 160 the data stored in the memory space identified by the identified PPN and communicates 170 the retrieved data to host filing system 105.
A drawback of the methods illustrated by FIGS. 1A-1D is the large amount of memory required to maintain the logical-to-physical address table in the memory device. In addition to the logical-to-physical address table, though not described above, the file transfer layer 100 must maintain a bitmap to identify the status (e.g., free space, used space) of every data page in the storage device.
FIG. 2A illustrates a related-art method of storing data in a memory device using nameless writes. FIG. 2B illustrates the related-art method of FIG. 2A pictorially. According to this method, a flash translation layer 200 receives 210 data from a host file system 205. Flash translation layer 200 stores 220 the received data within a page of a nonvolatile memory identified by a PPN. Flash translation layer 205 communicates 230 the PPN where the data is stored within the memory device to host file system 205. Host file system 205 maintains PPNs for all pages of the memory device in a file allocation table or Mode table.
FIG. 2C illustrates a related-art method of retrieving data stored in a memory device using nameless writes. FIG. 2D illustrates the related-art method of FIG. 2C pictorially. According to the method, flash translation layer 200 receives 250 a PPN from host file system 205. Flash translation layer 200 retrieves 260 the data stored at the received PPN of the memory device and communicates 270 the retrieved data to host file system 205.
Host file system 205 maintains a file allocation table or Mode table for every file stored within every memory block. The logical-to-physical address table described in connection with FIGS. 1A-1D is eliminated from the file translation layer 200, thus freeing a large amount of memory. For example, this can enable a reduction of the amount of RAM required for the storage device. Furthermore, the file translation layer does not update a logical-to-physical address for data read or write operations.
FIG. 3A illustrates a related-art, garbage-collection operation performed using the nameless-writes methodology for managing memory. FIG. 3B illustrates a related-art file allocation table maintained by a host file system during the garbage-collection operation illustrated by FIG. 3A. As illustrated in FIG. 3A, block 0 contains valid pages A through E and multiple invalid pages of data. So as to recover the memory space containing the invalid pages, flash translation layer 200 moves valid pages A through E to block 1 of the memory and frees all of the pages within block 0. After the garbage-collection operation illustrated by FIG. 3A is completed, the file allocation table illustrated by FIG. 3B now contains outdated PPN information.
More specifically, the file allocation table illustrated by FIG. 3B indicates that page A is stored in page 0 of block 0, page B is stored in page 2 of block 0 and page C is stored in page 5 of block 0, in accordance with their original storage locations illustrated by the left-side pane of FIG. 3A. However, after the valid pages of block 0 are moved to block 1 by the garbage-collection operation illustrated by the right-side pane of FIG. 3A, the file allocation table should reflect that page A is stored in page 0 of block 1, page B is stored in page 1 of block 1 and page C is stored in page 2 of block 1.
FIG. 3C illustrates a related-art method of in-place garbage collection performed using the nameless-writes methodology for managing memory. According to this method, file translation layer 200 stores pages received from host file system 205 in a queue until the sum of the number of pages in the queue and the number of valid pages within a block is enough to fill a block of memory. As illustrated for an initial state in FIG. 3C, block 0 contains valid pages A through E and four invalid pages. File translation layer 200 has stored pages F through I, which were received from host file system 205, in a queue. Thus, file translation layer 200 has enough pages to fill a block of memory.
To execute the in-place garbage collection, file translation layer 200 will ultimately store both the valid pages of block 0 and the pages temporarily stored within the queue in block 0. To accomplish this, file translation layer 200 must erase the invalid pages from block 0. However, file translation layer 200 can only erase an entire block, not individual pages within the block. Therefore, file translation layer 200 copies valid pages A through E to a dynamic random-access memory (DRAM), as illustrated in the second pane of FIG. 3C. Thereafter, file translation layer 200 erases all of the pages of block 0, as illustrated in the third pane of FIG. 3C. The in-place garbage-collection operation is completed by file translation layer 200 copying valid pages A through E from the DRAM to block 0 in the same page locations they had in their initial state and copying pages F through I from the queue to the remaining page locations of block 0.
The in-place garbage-collection operation illustrated by FIG. 3C overcomes the problem of creating outdated PPN information in the file allocation table. However, a very large DRAM is required to temporarily hold all of the valid pages while the block from which they came is erased. Also, a large capacitor or battery is required to maintain power for the DRAM in the event of a power failure; otherwise, the data stored in the DRAM will be lost during such power failure.
Additionally, the in-place garbage-collection operation produces inefficiencies if the sum of the queued pages and valid pages within a block are insufficient to fill the block. In this event, file translation layer 200 either creates a block with unused page space or waits for the queue to fill before completing the garbage collection. If the garbage collection has already begun, the DRAM will consume power while it temporarily stores the valid pages copied from the block undergoing the garbage collection.
Another way for overcoming the problem of creating outdated PPN information in the file allocation table is to update the file allocation table within host file system 205 through a call-back operation. This may be accomplished by having file translation layer 200 communicate both the outdated PPNs and the new, replacement PPNs to host file system 205. Host file system 205 updates the file allocation table with the received information and informs file translation layer 200 that the update is complete. However, the call-back operation is non-standard and requires processor resources of host file system 205.
FIG. 3D illustrates a related-art method of wear leveling using the nameless-writes methodology of managing memory. As illustrated in FIG. 3D, block 0 is a fresh block of a memory containing valid pages A through I of data. Block 1 is a worn block of the memory containing nothing but free pages. File translation layer 200 copies valid pages A through I from block 0 to block 1 and erases all pages within block 0. Thus, valid pages A through I are transferred from fresh block 0 to worn block 1 by the wear-leveling operation. However, just as was the case with the garbage-collection operation illustrated by FIG. 3A, the file allocation table maintained by host file system 205 is outdated, as similarly illustrated in FIG. 3B. The file allocation table must be updated using the call-back operation described above.
The present disclosure builds upon the benefits of the nameless-writes methodology for managing a nonvolatile memory by overcoming drawbacks of the nameless-writes methodology. The benefits of nameless writes are the absence of a logical-block-address bitmap during file operations, the absence of a logical-to-physical table for writing data, and the absence of a logical-to-physical table access for data read operations.